#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 30
#define INFINITY 9999
typedef struct arc
{
    int weight;
    int iverxt, jverxt;
    struct arc *iarc, *jarc;
};
typedef struct node
{
    int data;
    arc *firstarc;
};

typedef struct Adja_list
{
    int nodenum;
    int arcnum;
    node nodes[MAXSIZE];
};

Adja_list transform_adja_list(int a[][MAXSIZE], int data[], int n)
{
    Adja_list g;
    for (int k = 0; k < n; k++)
    {
        g.nodes[k].firstarc = NULL;
        g.nodes[k].data = data[k];
    }
    g.nodenum = n;
    g.arcnum = 0;
    //masterpiece!!! creat graph just by once traversal
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = i; j >= 0; j--) //O(n²/2)
        {
            if (a[i][j] != 0 && a[i][j] != INFINITY)
            {
                arc *temp_arc = (arc *)malloc(sizeof(arc));
                g.arcnum++;
                temp_arc->weight = a[i][j];
                temp_arc->iverxt = i;
                temp_arc->jverxt = j;
                temp_arc->iarc = temp_arc->jarc = NULL;

                temp_arc->iarc = g.nodes[i].firstarc;
                g.nodes[i].firstarc = temp_arc;

                temp_arc->jarc = g.nodes[j].firstarc;
                g.nodes[j].firstarc = temp_arc;
            }
        }
    }
    return g;
}
void vist(Adja_list g)
{
    printf("traversal graph:\n");
    for (int i = 0; i < g.nodenum; i++)
    {
        printf("%3d", g.nodes[i].data);
        arc *p = g.nodes[i].firstarc;
        while (p)
        {
            printf(" (%2d,%2d) ", p->iverxt, p->jverxt);
            p->iverxt == i ? p = p->iarc : p = p->jarc;
        }
        printf("\n");
    }
}
int main()
{
    /*******************code*******************/
    int data2[] = {0, 1, 2, 3, 4};
    int weight_matrix[30][30] = {{0, 1, INFINITY, 1, INFINITY},
                                 {1, 0, 1, INFINITY, 1},
                                 {INFINITY, 1, 0, 1, 1},
                                 {1, INFINITY, 1, 0, INFINITY},
                                 {INFINITY, 1, 1, INFINITY, 0}};
    Adja_list G = transform_adja_list(weight_matrix, data2, 5);
    vist(G);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
